Longest Bitonic Subsequence

Statement#

Suppose you are given an array, nums, containing positive integers. You need to find the length of the longest bitonic subsequence in this array. A bitonic subsequence can be of the following three types:

• It can consist of numbers that are first increasing and then decreasing. For example, $(2, 6, 9, 3, 2)$.

• It can consist of numbers that are only increasing (where the decreasing part at the end is empty). For example, $(2, 3, 7, 9)$.

• It can consist of numbers that are only decreasing (where the increasing part at the start is empty). For example, $(15, 12, 5, 3, 2, 1)$.

Let’s say you have the following array:

• $[19, 20, 5, 3, 13]$

The longest bitonic subsequence from this array is $(19, 20, 5, 3)$, and the length of this subsequence is $4$.

Constraints:

• $1\leq$ nums.length $\leq 900$
• $1\leq$ nums[i] $\leq 10^4$

Examples#

Try it yourself#

Implement your solution in the following playground.

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution#

We will first explore the naive recursive solution to this problem and then see how it can be improved using the Longest Common Substring dynamic programming pattern.

Naive approach#

A naive approach would be to generate combinations of all possible bitonic subsequences in the array and select the one with the maximum length.

For example, we have the following array:

nums: $[5, 11, 7, 10]$

To find the length of the longest bitonic subsequence, we try all possible combinations:

• $(5)$, length = $1$

• $(5, 11)$, length = $2$

• $(5, 7)$, length = $2$

• $(5, 10)$, length = $2$

• $(5, 11, 7)$, length = $3$

• $(5, 11, 10)$, length = $3$

• $(5, 7, 10)$, length = $3$

• $(11)$, length = $1$

• $(11, 7)$, length = $2$

• $(11, 10)$, length = $2$

• $(7)$, length = $1$

• $(7, 10)$, length = $2$

• $(10)$, length = $1$

We select the bitonic subsequence with length $3$.

We will use a Boolean variable, is_decreasing, which will have the following properties:

• It will be FALSE if we’re at the increasing part of the subsequence.

• It will be TRUE if we’re at the decreasing part of the subsequence.

Here is how the algorithm works:

• Base case: If we’ve passed the end of the array, we return $0$.

• If we’re at the first element, we have three choices:

  • Exclude the element from the subsequence by default.

  • Include the element in the subsequence and then take the maximum length of moving to either the increasing or decreasing part of the subsequence for the next element.

  • The maximum length of either, including or excluding the current element, is selected.

• If is_decreasing is FALSE, we’re in the increasing part of the subsequence. We now have three choices:

  • Exclude the element from the subsequence by default.

  • If nums[curr] > nums[prev], the element can be included to make a valid increasing subsequence; so, we include it and take the maximum length of moving to either the increasing or decreasing part of the subsequence for the next element.

  • We select the maximum length of the subsequence from either including or excluding the element from the above computations.

• Otherwise, if is_decreasing is TRUE, we’re in the decreasing part of the subsequence. We now have two choices:

  • Exclude the element from the subsequence by default.

  • If nums[curr] < nums[prev], the element can be included to make a valid decreasing subsequence; so, we take the maximum of either, including or excluding the number.

Let’s implement the algorithm as discussed above:

Note: Please observe that if you include the test case commented out in the driver code, the solution is likely to time out. Try to solve the larger problem using the dynamic programming solutions provided below and see the difference.

Time complexity#

The time complexity of the naive approach is $O(3^n)$, where $n$ is the total number of elements in the array.

Space complexity#

As the maximum depth of the recursive call tree is $n$, and each call stores its data on the stack, the space complexity of this approach is $O(n)$.

Optimized solution using dynamic programming#

Now, let us improve the recursive solution using top-down and bottom-up approaches.

Top-down solution#

The top-down solution, commonly known as the memoization technique, is an enhancement of the recursive solution. It overcomes the problem of calculating redundant solutions over and over again by storing them in a table. In the recursive approach, the following three variables kept changing:

• The current array index, curr.
• The index of the last element in the subsequence, prev.
• The boolean variable, is_decreasing, which indicated whether we were in the increasing or decreasing part of the subsequence.

We will use a 3-D table with the above three indexes to uniquely identify and store a subproblem. At any later time, if we encounter the same sub-problem, we can return the stored result from the table with an $O(1)$ look-up instead of re-calculating that subproblem.

Let’s implement the algorithm as discussed above:

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

As we avoided redundant calculations by storing all the intermediate results in a 3-D table, the time complexity of this approach is reduced to $O(n^2)$, where $n$ is the number of elements in the array.

Space complexity#

We now need $O(n^2)$ space in memory to store intermediate values.

Bottom-up solution#

The bottom-up solution, also known as the tabulation technique, is an iterative method of solving dynamic programming problems.

For an array, nums, with length n, we do the following for every index, i.

• We calculate the length of the longest increasing subsequence from nums[0]…nums[i].

• We calculate the length of the longest increasing subsequence from nums[n - 1]…nums[i].

• We add the two lengths and subtract them by $1$ to get the length of the longest bitonic subsequence at nums[i].

The following illustration explains the above approach:

We declare two 1-D arrays of length $n$, which are initialized to $1s$. They have the following properties:

• lis_forward: This array contains the LIS from nums[0]…nums[i] for every $i$ in nums.

• lis_backward: This array contains the LIS from nums[n - 1]…nums[i] for every $i$ in nums.

We fill the lis_forward array by traversing the nums array from left to right:

• At each element of the array, nums[i], we use a nested loop to traverse all the elements, nums[j], that come before it:

  • For every nums[j], we check two conditions:

    • The first condition is nums[j] < nums[i], which checks if nums[j] can be included to make a valid increasing subsequence from nums[0]…nums[i]. If this condition is TRUE, we check the next condition. Otherwise, we skip this element by moving to the next iteration of the nested loop.

    • The second condition is 1 + lis_forward[j] > lis_forward[i] which checks if including nums[j] in the increasing subsequence from nums[0]…nums[i] will result in an increasing subsequence of a greater length than the existing subsequence length in list_forward[i]. If this condition is TRUE, we include nums[j] in the increasing subsequence by updating the value stored in lis_forward[i] to 1 + lis_forward[j]. Otherwise, we skip this element by moving to the next iteration of the nested loop.

We fill the lis_backward array by traversing the nums array from right to left:

• At each element of the array, nums[i], we use a nested loop to traverse all the elements, nums[j], that come before it:

  • For every nums[j], we check two conditions:

    • The first condition is nums[j] < nums[i], which checks if nums[j] can be included to make a valid increasing subsequence from nums[n - 1]…nums[i]. If this condition is TRUE, we check the next condition. Otherwise, we skip this element by moving to the next iteration of the nested loop.

    • The second condition is 1 + lis_backward[j] > lis_backward[i] which checks if including nums[j] in the increasing subsequence from nums[n - 1]…nums[i] will result in an increasing subsequence of a greater length than the existing subsequence length in lis_backward[i]. If this condition is TRUE, we include nums[j] in the increasing subsequence by updating the value stored in lis_backward[i] to 1 + lis_backward[j]. Otherwise, we skip this element by moving to the next iteration of the nested loop.

We initialize a variable result, set to $1$. This variable will be used to store the length of the longest bitonic subsequence in nums. We perform a final loop to simultaneously traverse the lis_forward and lis_backward arrays:

• At each index, i, we will calculate the length of the longest bitonic subsequence till nums[i] through the formula: lis_forward[i] + lis_backward[i] - 1.
• We store this value in a variable, length.
• We set result to the max of the existing value of result and length.

When the loop ends, we return result.

Let’s look at the following illustration to get a better understanding of the solution:

Let’s implement the algorithm as discussed above:

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

As we’re using nested loops to populate the two 1-D arrays to store the results of sub-problems that would be used later on, therefore, the time complexity of this approach will be $O(n^2)$.

Space complexity#

We need $O(n)$ space in memory to store the intermediate values.